package com.salim.leetcode.$138;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class CopyListWithRandomPointer {
    //这个写法还可以优化 直接使用HashMap<Node,Node>保存映射关系
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        List<Node> oldList = new ArrayList<>();
        List<Node> newList = new ArrayList<>();
        HashMap<Node,Integer> hashMap = new HashMap<>();
        oldList.add(head);
        hashMap.put(head,0);

        Node newHead = new Node(head.val);
        newList.add(newHead);

        int index = 1;
        while(head.next!=null){
            oldList.add(head.next);
            hashMap.put(head.next,index);
            index++;
            Node newTemp = new Node(head.next.val);
            newList.add(newTemp);
            newHead.next = newTemp;
            head = head.next;
            newHead = newHead.next;
        }
        for(int i=0;i<oldList.size();i++){
            if(oldList.get(i).random!=null){
                newList.get(i).random = newList.get(
                    hashMap.get(
                        oldList.get(i).random
                    )
                );
            }
        }
        return newList.get(0);
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
